package com.lry.basic.algorithm.common;

import java.util.ArrayList;
import java.util.List;

class PathInZigZagTree {

    public static void main(String[] args) {
        System.out.println(pathInZigZagTree(14));
    }
    public static List<Integer> pathInZigZagTree(int label) {
        List<Integer> list = new ArrayList();
        list.add(label);

        while(label!=1){
            label = parent(label);
            list.add(0,label);
        }

        return list;
    }

    public static int parent(int label){
        int n=0;

        while(label >= (int)Math.pow(2,n)){
            n++;
        }
        int left = (int)Math.pow(2,n-1);
        int right = (int)Math.pow(2,n)-1;

        return (left+right-label)/2;
    }
}